#include <vector>
#include <unordered_map>
#include <queue>
#include <iostream>

using namespace std;

class myComparison
{
public:
    bool operator()(const pair<int, int> & lhs, const pair<int, int> & rhs)
    {
        return lhs.second > rhs.second;
    }
};

class Solution 
{
public:
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        unordered_map<int, int> freq_map;
        for(int i = 0; i < nums.size(); i++)
        {
            freq_map[nums[i]]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, myComparison> pri_que;
        for(auto it = freq_map.begin(); it != freq_map.end(); it++)
        {
            pri_que.push(*it);
            if(pri_que.size() > k)
            {
                pri_que.pop();
            }
        }

        vector<int> result;
        for(int i = 0; i < k; i++)
        {
            result.push_back(pri_que.top().first);
            pri_que.pop();
        }
        return result;
    }
};

int main()
{
    Solution solution;

    // 测试案例1: 基本情况
    vector<int> test1 = {1, 1, 1, 2, 2, 3};
    int k1 = 2;
    cout << "测试案例1: nums = [1,1,1,2,2,3], k = 2" << endl;
    vector<int> result1 = solution.topKFrequent(test1, k1);
    cout << "结果: [";
    for (int i = 0; i < result1.size(); i++) {
        cout << result1[i];
        if (i < result1.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: [1,2] 或 [2,1]" << endl << endl;

    // 测试案例2: 只有一个元素
    vector<int> test2 = {1};
    int k2 = 1;
    cout << "测试案例2: nums = [1], k = 1" << endl;
    vector<int> result2 = solution.topKFrequent(test2, k2);
    cout << "结果: [";
    for (int i = 0; i < result2.size(); i++) {
        cout << result2[i];
        if (i < result2.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: [1]" << endl << endl;

    // 测试案例3: 复杂情况
    vector<int> test3 = {1, 2, 1, 2, 1, 2, 3, 1, 3, 2};
    int k3 = 2;
    cout << "测试案例3: nums = [1,2,1,2,1,2,3,1,3,2], k = 2" << endl;
    vector<int> result3 = solution.topKFrequent(test3, k3);
    cout << "结果: [";
    for (int i = 0; i < result3.size(); i++) {
        cout << result3[i];
        if (i < result3.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: [1,2] 或 [2,1]" << endl << endl;

    // 测试案例4: 所有元素频率相同
    vector<int> test4 = {1, 2, 3, 4};
    int k4 = 2;
    cout << "测试案例4: nums = [1,2,3,4], k = 2" << endl;
    vector<int> result4 = solution.topKFrequent(test4, k4);
    cout << "结果: [";
    for (int i = 0; i < result4.size(); i++) {
        cout << result4[i];
        if (i < result4.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: 任意2个元素" << endl << endl;

    // 测试案例5: 负数情况
    vector<int> test5 = {-1, -1, -2, -2, -2, 0, 0, 0, 0};
    int k5 = 2;
    cout << "测试案例5: nums = [-1,-1,-2,-2,-2,0,0,0,0], k = 2" << endl;
    vector<int> result5 = solution.topKFrequent(test5, k5);
    cout << "结果: [";
    for (int i = 0; i < result5.size(); i++) {
        cout << result5[i];
        if (i < result5.size() - 1) cout << ",";
    }
    cout << "]" << endl;
    cout << "预期: [0,-2] 或 [-2,0]" << endl << endl;

    return 0;
}